// 文件名必须是 Solution.java
public class Solution {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        // 头插法
        public void insertAtHead(int value) {
            ListNode newNode = new ListNode(value);
            newNode.next = this.next;
            this.next = newNode;
        }

        // 尾插法
        public void insertAtTail(int value) {
            ListNode newNode = new ListNode(value);
            if (this.next == null) {
                this.next = newNode;
            } else {
                ListNode current = this.next;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }

        // 打印链表
        public void printList() {
            ListNode current = this.next; // 跳过头节点
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 处理一般情况
        ListNode prev = null;
        ListNode cur = head.next; // 跳过头节点
        while (cur != null) {
            ListNode next = cur.next; // 保存下一个节点
            cur.next = prev; // 反转当前节点的指针
            prev = cur; // 更新 prev 和 cur 的指向
            cur = next;
        }
        head.next = prev; // 将头节点的 next 指向新的头节点
        return head;
    }

    public static void main(String[] args) {
        // 创建一个链表：1->2->3->4->5
        ListNode head = new ListNode(); // 创建一个头节点
        head.insertAtTail(1);
        head.insertAtTail(2);
        head.insertAtTail(3);
        head.insertAtTail(4);
        head.insertAtTail(5);

        // 打印原始链表
        System.out.println("原始链表：");
        head.printList();

        // 调用 reverseList 方法反转链表
        Solution solution = new Solution();
        solution.reverseList(head);

        // 打印反转后的链表
        System.out.println("反转后的链表：");
        head.printList();
    }
}



